package q79_exist;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
    }

    public boolean exist(char[][] board, String word) {
        boolean flag = false;
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 遍历在矩阵中的每一个字符，直到找到word的第一个字符开始进行迭代
                flag = checkCharacter(board, visited, word, i, j, 0);
                if (flag){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean checkCharacter(char[][] board,boolean[][] visited, String word, int row, int col, int startIndex) {
        // 先设定初始条件，如果这个位置的字符不是word[Index]的字符，就直接返回，false
        if (board[row][col] != word.charAt(startIndex)) {
            return false;
        }
        // 如果Index到达了最后，意味着递归也就结束了
        if (startIndex == word.length() - 1) {
            return true;
        }

        // 前面的两者没有满足，意味着还需要寻找剩下的字符串，那么先将这个位置设置为已经搜寻
        visited[row][col] = true;

        // 搜索四个方向是否存在下一个字符
        boolean res = false;
        int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        for (int i = 0; i < 4; i++) {
            // 移动后的row以及col位置
            int rowMove = row + dirs[i][0];
            int colMove = col + dirs[i][1];
            // 首先保证不溢出
            if (rowMove >= 0 && rowMove <= board.length - 1 && colMove >= 0 && colMove <= board[0].length - 1 ){
                // 然后保证未访问
                if (!visited[rowMove][colMove]) {
                    boolean flag = checkCharacter(board, visited, word, rowMove, colMove, startIndex + 1);
                    if (flag) {
                        // 注意，这里只能结束循环，而不能直接return true，因为还要将visited状态设置回来
                        res = true;
                        break;

                    }
                }

            }
        }

        // 找完还需要重新把位置的搜寻状态设置回来
        visited[row][col] = false;

        return res;
    }
}
